1. Field of the Invention
The present invention relates to the field of communications, and to an apparatus and method for congestion control in high speed networks. More particularly, the present invention relates to flow control techniques and the flow control of Available Bit Rate (ABR) traffic in, for example, Asynchronous Transfer Mode (ATM) networks.
2. Background and Material Information
With advanced ATM technologies, future high speed networks will be able to support a wide spectrum of applications with diverse traffic characteristics and service requirements. Using ATM Forum terminologies, traffic is classified into three classes: Constant Bit Rate (CBR), Variable Bit Rate (VBR) and Available Bit Rate (ABR). The CBR and VBR traffic are transmitted in high priority with sufficient reservation of buffer space and link capacity; their arrival rate is normally not adaptable to the changing network environment. In contrast, the ABR traffic is transmitted in low priority using the remaining buffer space and link capacity; their arrival rate is constantly adjustable to avoid network congestion. For low complexity high speed operation, the end to end flow control approach is found superior to that of link by link flow control. Further, the traditional window based flow control is no longer effective in high speed networks and is replaced by rate based control. In the rate based control design, the arrival rate of each ABR connection is dynamically adapted based on network feedback information.
A simple rate based control scheme uses single bit feedback information from the network. An example of such a control scheme is described in M. HLUCHYJ and N. YIN, "On Closed-loop Rate Control for ATM Networks," Proc. INFO-COM '94, pp.99-108 (1994), the disclosure of which is expressly incorporated herein by reference in its entirety. With single-bit feedback, a bit is marked at switching nodes or destination based on some preset congestion status. All the ABR sources will then adjust their transmission rate, based upon the single bit observation. An exemplary single-bit feedback scheme is called negative polarity feedback, and is described in J. C. BOLOT and A. SHANKAR, "Dynamic Behavior of Rate-based Flow Control Mechanisms," ACM Comp. Comm. Review, Vol. 20, No. 2, pp. 35-49 (1992), the disclosure of which is expressly incorporated herein by reference in its entirety. In negative polarity feedback, each ABR source reduces its transmission rate exponentially once receiving the negative feedback bit, otherwise each source keeps increasing its transmission rate linearly.
As indicated in the study described in R. JAIN et al., "The OSU Scheme for Congestion Avoidance Using Explicit Rate Indication," OSU Technical Report, September 1994, the disclosure of which is expressly incorporated herein by reference in its entirety, a single-bit rate based control is too slow to react to the rapidly changing traffic environment and an explicit rate control scheme should be designed to enhance control performance. One scheme was proposed by JAIN and his co-workers at Ohio State University. In the OSU scheme, a load factor is periodically computed at the congested node, the load factor being the ratio of present aggregate ABR rate to its desired rate. The rate of each individual ABR source in the next period is then simply equal to its current rate divided by the load factor. For example, if the aggregate rate is only one half of its desired rate, each source rate will be doubled in the next period.
The major advantage of most proposed single bit and explicit rate control schemes is their simplicity in implementation. However, to achieve such simplicity neither a dynamic control model nor round trip multiloop delays are considered in the above noted schemes. Yet, there is a price for simplicity which should be considered. First, most existing control schemes induce significant low frequency high magnitude oscillations in each feedback ABR control loop, where the oscillation frequency is directly associated with the round trip delay of each loop. It is intuitively clear that such inherent low frequency traffic oscillations will cause substantial oscillations in queuing process. As a result, a large buffer capacity has to be reserved at each node to absorb the ABR traffic oscillations. Second, the stability of the control schemes is highly sensitive to the high priority CBR/VBR traffic characteristics.
Another problem with most existing attempts on ABR feedback control design is they generally neglect the effect of multiple feedback loop delays and high priority traffic transmission. With multiloop delays, the already existing low frequency high magnitude oscillations of ABR traffic within each loop can become much worse. With high priority traffic transmission, the original control stability conditions can be ruined.
The closed loop stability problem is a major issue fi)r any feedback control scheme. Its solution requires the knowledge of round trip delays of all ABR connections. In fact, the round trip delay is the main obstacle that prevents the prior systems from achieving good congestion control performance; especially within a wide area network, the round trip delay of individual ABR connections can be vastly different. For systems with multiple delays, their feedback controller must be carefully designed to provide closed loop stability, otherwise the systems can easily become unstable.
The study in L. BENMOHAMED and S. MEERKOV, "Feedback Control of Congestion in Store-and-Forward Networks: The Described Case in Single Congestion Node," IEEE/ACM Trans. Networking, Vol. 1, No. 6, December 1993, pp. 693-708, the disclosure of which is expressly incorporated herein by reference in its entirety, considers round trip delays and analyzes the closed loop stability of an explicit rate control scheme in the absence of high priority traffic. In the disclosed scheme, a fluid flow queuing model is adopted and the queue size at the bottleneck node is used as the feedback information for the ABR traffic adaption. The feedback controller in BENMOHAMED et al. is designed only with the requirement of closed loop stability. No other performance criteria such as steady state error is considered.
In existing binary bit Available Bit Rate (ABR) congestion control schemes, nodal congestion is often detected by comparison of present queue size with a predetermined threshold. However, the queue threshold detection schemes have disadvantages. First, no congestion can be detected until the queue is longer than the threshold. Second, although the congestion is readily removed as the queue starts dropping, the detection of when the queue dropped below the threshold has unnecessarily extended the congestion period. The delayed detection followed by unnecessary extension of congestion periods significantly increases the oscillation period as well as the oscillation magnitude of ABR traffic within the network, causing a large consumption of buffer resources.
Therefore, despite the advances, congestion control of high speed network switches, such as ATM switches, is still inadequate. Large buffers are required to handle the overflow of data due to inaccurate detection of the network congestion. Moreover, multiple feedback loop delays and high priority traffic transmission has been neglected in existing feedback control designs. Thus, there exists a need for a system which accurately detects the congestion in an ATM network in order to optimize the throughput of ATM networks by controlling the flow of the ABR traffic.